1. Field of the Invention
The present invention relates to methods for using a tree structure in a data search. More particularly, the present invention relates to a method for searching the tree structure of a set of data stored on a computer-readable medium to manipulate target data.
2. Description of Related Art
The use of a tree structure to represent ordered data sets on a computer is known. See Non-Patent Document 1. The tree structure is represented by nodes and edges. The nodes are hierarchically associated with each other and with the edges. A single node at the highest layer of the tree structure is referred to as a root node, while nodes at the lowest layer of the tree structure are referred to as leaf nodes. For example, a tree structure is often used in the creation of an index of a database.
Operations, such as search, insertion, and deletion, are performed on data that can be represented by a tree structure. In addition, varieties of tree structures are known. These include: the B tree, Non-Patent Document 2; the B+ tree derived from the B tree, the T tree particularly used as a tree structure in a memory, Non-Patent Document 3; and the B-link tree which provides improved throughput and scalability, Non-Patent Document 4. Scalability is one kind of extensibility and particularly indicates a capability for coping with an increase in the amount of work which can be performed. When an apparatus, such as a computer, uses a tree structure, a synchronization operation or mechanism, such as a lock or a semaphore, is used to realize parallel operations.
FIGS. 17(a) to 17(c) illustrate tree structures according to related art. These tree structures are represented with nodes, shown as rectangles, and edges or links that connect the nodes. The nodes are associated with various kinds of data, shown as number quantities within the nodes, representing, e.g., a value, a condition, another data structure, and another tree structure. For example, the data can be a value or a set of values, which can serve as a criterion in the comparison of a magnitude relation.
Each node in the tree structure has zero or more child nodes, which are generally located at lower layers in the tree structure. That is, the tree structure includes child nodes that constitute a plurality of layers. A node at the top of the tree structure is referred to as a root node. The nodes at the bottom of the tree structure are referred to as leaf nodes. The tree structures shown in FIGS. 17(a) to 17(c) can be used in a process for looking up data for use in a specific search, also referred to as a search key or simply referred to as a key, on a storage medium.
FIG. 17(a) is a block diagram illustrating the concept of a B+ tree according to the related art. Data in the root node is shown at the top layer of FIG. 17(a), while a set of data stored on a computer-readable medium is shown at the bottom. An index that is a process for searching for target data from the computer-readable medium is shown between the top layer and the bottom layer.
The index can include, for example, a branching condition. A plurality of pieces of data at the bottom layer can be stored on a computer-readable medium in accordance with a magnitude relation between the data pieces. First, a specific value is set as the target data located at the top layer before a search is started. In the intermediate process, an index that can handle the target data is specified using indices representing a magnitude relation for some pieces of data on the computer-readable medium in the B+ tree in accordance with a rule. An example of a rule is that another index indicating a smaller value range is used if the value of the target data is smaller than a range indicated by a specific index. The target data is then used as an input of magnitude-relation conditional branching of the specified index. On the basis of whether a determination result regarding this branch condition is true or not, a storage area that can include the target data can be narrowed down or specified from a whole area of the recording medium shown at the bottom layer in FIG. 17(a).
FIG. 17(b) is a block diagram showing an example of a T tree according to the related art. The T tree shown in FIG. 17(b) can be a binary search tree. For example, a universal set of data stored on a computer-readable medium can be exclusively divided into a plurality of subsets on the basis of a magnitude relation between values by which the T tree can be constructed. Each of the subsets can include a boundary condition regarding values as an index and information regarding links to other neighboring subsets that have consecutive boundaries. Target data can be searched in accordance with a known search algorithm, such as, for example, a preorder search, an inorder search, or a postorder search. In this manner, a specific subset including the target data can be narrowed down or specified.
FIG. 17(c) is a block diagram showing an example of a B-link tree according to the related art. Although the B-link tree shown in FIG. 17(c) resembles the B tree shown in FIG. 17(a), each node of the B-link tree structure can include a “high key”, which is information on the maximum value that this node or child nodes at the lower layers can have. In FIG. 17(c), the “high key” of each node is illustrated having a thick frame.
Furthermore, nodes in the same layer can be linked to one another in one direction, e.g., toward the right in the drawing, with a unidirectional list in the B-link tree according to the related art. When a node is deleted, a pointer called “outlink” is associated from the deleted node to a neighboring node on the left. To execute a search in a specific node, acquisition and/or release of a lock on the specific node are executed in the B-link tree.